# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2021/3/14 11:15
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : kNN.py
@Version     : Version 1.0.0
@Description : TODO 实现k近邻算法
@Created By  : PyCharm
"""
from numpy import *


def create_dataset():  # 保证每一次使用的训练数据集都是一样的
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels


def knn_classifier0(in_x, dataset: ndarray, labels, k):
    """
    实现KNN算法的分类器
    :param in_x:特征向量x
    :param dataset:输入的训练样本集
    :param labels:标签向量
    :param k:选择最近邻居数目
    :return:预测标签值
    """
    dataset_size = dataset.shape[0]
    # 计算输入特征向量x与所有样本点的距离，使用欧氏距离公式
    diff_mat = tile(in_x, (dataset_size, 1)) - dataset  # 计算差矩阵
    sq_diff_mat = diff_mat ** 2
    sq_distances = sq_diff_mat.sum(axis=1)
    distances = sq_distances ** 0.5
    sorted_dist_indices = distances.argsort()
    class_count = {}
    # 选择距离最小的前k个点
    for i in range(k):
        vote_label = labels[sorted_dist_indices[i]]
        class_count[vote_label] = class_count.get(vote_label, 0) + 1  # 统计每一种标签类出现的数量
    # 对前k个距离最近的样本按照标签出现次数从大到小排序
    sort_class_count = sorted(class_count.items(), key=lambda x: x[1], reverse=True)
    return sort_class_count[0][0]


def file2matrix(filename, charset="utf-8"):
    """
    实现数据准备
    :param filename: 训练数据集文件
    :param charset:字符集
    :return:特征向量矩阵，标签向量
    """
    file = open(filename, encoding=charset)
    lines_list = file.readlines()
    number_of_lines = len(lines_list)
    features_matrix = zeros((number_of_lines, 3))  # 初始化特征矩阵
    class_labels_vector = []
    index = 0
    for line in lines_list:
        line = line.strip("\n")
        list_from_line = line.split("\t")
        features_matrix[index, :] = list_from_line[:3]  # 数据类型需要调整为float
        class_labels_vector.append(list_from_line[-1])
        index += 1
    return features_matrix, class_labels_vector


def auto_norm(dataset: ndarray):
    """
    归一化数据集
    :param dataset: 数据集
    :return: 归一化数据集，数据集特征值范围，最小值向量
    """
    min_values = dataset.min(axis=0)
    max_values = dataset.max(axis=0)
    interval = max_values - min_values
    row = dataset.shape[0]
    norm_dataset = (dataset - tile(min_values, (row, 1))) / tile(interval, (row, 1))
    return norm_dataset, interval, min_values


def dating_class_test(filename, ho_ratio=0.10, k=4):
    """
    约会数据集KNN算法测试
    :param filename: 文件路径
    :param ho_ratio: 随机测试集占数据集比重
    :param k: 最近邻样本点数
    :return: 错误率
    """
    # 准备数据集和标签向量
    dating_dataset, dating_labels = file2matrix(filename)
    # 对数据集归一化
    norm_mat, ranges, minimums = auto_norm(dating_dataset)
    row = norm_mat.shape[0]
    num_test_vectors = int(ho_ratio * row)  # 测试集特征向量行数
    error_count = 0
    for i in range(num_test_vectors):
        classifier_result = knn_classifier0(norm_mat[i, :],
                                            norm_mat[num_test_vectors:row, :],
                                            dating_labels[num_test_vectors:row], k)
        if classifier_result != dating_labels[i]:
            error_count += 1
    return error_count / num_test_vectors


if __name__ == '__main__':
    # group0, labels0 = create_dataset()
    # print(knn_classifier0([0, 0], group0, labels0, 3))
    path = r"datingTestSet.txt"
    # 调优超参数
    ratio_range = [0.1 + i * 0.01 for i in range(21)]
    error_rate_list = []
    for k in range(3, 11):  # k= 3-10
        for ratio in ratio_range:  # ratio=0.1-0.3
            error_rate = dating_class_test(path, ratio, k)
            error_rate_list.append((ratio, k, error_rate))
    error_rate_list.sort(key=lambda x:x[-1])
    print("最优测试集比重ratio={}\n最优最近邻数k={}\n最低错误率error_rate={}".format(*error_rate_list[0]))
